package com.xiaoyu.linkedArray;

/**
 * @program: DS_and_A
 * @description: 相交链表
 *
 * 编写一个程序，找到两个单链表相交的起始节点。
 *
 * 如下面的两个链表：
 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Reference of the node with value = 8
 * 输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，
 * 链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 *
 *
 * @author: YuWenYi
 * @create: 2021-05-26 18:31
 **/
public class GetIntersectionNode_160 {

    /*
    * 自己的解法:
    * 先求出两个链表的长度
      再移动较长的那个链表,移动的长度是两个链表的长度之差
      此时两个链表一样长了,此时同步移动然后找共同点就可以了!
    *
    * */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null; //特判
        ListNode p1 = headA,p2 = headB;
        //求链表A的长度
        int lenA = linkedLength(p1);
        p1 = headA;
        //求链表B的长度
        int lenB = linkedLength(p2);
        p2 = headB;
        //移动链表
        if (lenA > lenB){
            p1 = moveEle(p1, lenA - lenB);
        }
        if (lenA < lenB){
            p2 = moveEle(p2, lenB - lenA);
        }
        //到这里两个链表一样长了,移动哪个都一样
        while (p1 != null){
            if (p1 == p2){
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

    public ListNode moveEle(ListNode node,int moveLen){
        while (moveLen > 0){
            node = node.next;
            moveLen--;
        }
        return node;
    }
    public int linkedLength(ListNode node){
        int len = 0;
        while (node!=null){
            len++;
            node = node.next;
        }
        return len;
    }


    //解法二:绝了
    /*
    * 思路就是:p1遍历完自己的链表后,再去遍历另一条链表,p2同理,如果有交点那么迟早都能遇到!
    * 如果没有交点,就会在两者都为null的时候退出
    *
    * 退出循环的方式有两种:1.同时指向公共结点 2.同时指向null
    * 若两链表 有 公共尾部 (即 c > 0c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
    * 若两链表 无 公共尾部 (即 c = 0c=0 ) ：指针 A , B 同时指向 null 。。
    *
    * */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null; //特判
        ListNode p1 = headA,p2 = headB;
        while (p1 != p2){
            p1 = p1 != null ? p1.next : headB;
            p2 = p2 != null ? p2.next : headA;
        }
        return p1;
    }

    public static void main(String[] args) {
        GetIntersectionNode_160 gi = new GetIntersectionNode_160();
        ListNode intersection = new ListNode(3, new ListNode(4, new ListNode(5)));

        ListNode headA = new ListNode(1,new ListNode(2));
        ListNode headB = new ListNode(8,new ListNode(9,new ListNode(10)));
        System.out.println(gi.getIntersectionNode1(headA, headB));
    }
}
